package leetcode.all;

import datastruct.tree.TreeNode;

import java.util.HashMap;

public class Solution889 {

    public static void main(String[] args) {
        int[] pre = {2,1};
        int[] pos = {1,2};
        TreeNode root = new Solution889().constructFromPrePost(pre,pos);
        System.out.println(root);
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        //为了能快速找到左子树的根节点，对post进行map
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < post.length; i++) {
            hashMap.put(post[i],i);
        }
        return construct(pre,post,0,pre.length-1,0,post.length-1,hashMap);
    }

    public TreeNode construct(int[] pre, int[] post, int pri, int prj, int poi, int poj, HashMap<Integer,Integer> hashMap) {
        if(pri>prj) return null;
        if(pri==prj) return new TreeNode(pre[pri]);
        int leftRootInPost = hashMap.get(pre[pri+1]);
        int leftPri = pri + 1;
        int leftPrj = pri + 1 + leftRootInPost - poi;
        int leftPoi = poi;
        int leftPoj = leftRootInPost;
        int rightPri = leftPrj + 1;
        int rightPrj = prj;
        int rightPoi = leftPoj + 1;
        int rightPoj = poj - 1;
        TreeNode root = new TreeNode(pre[pri]);
        root.left = construct(pre, post, leftPri, leftPrj, leftPoi, leftPoj, hashMap);
        root.right = construct(pre, post, rightPri, rightPrj, rightPoi, rightPoj, hashMap);
        return root;
    }
}
